資料結構

矩陣一般透過多維陣列展現，這也是為什麼在陣列介紹後我選擇接著矩陣討論。
如果是一個整數矩陣，C# 可以透過 int[][] 或是 int[,] 的方式來做矩陣宣告，取用元素的方式也會不一樣。
像上面兩個宣告做出來的矩陣叫做二維矩陣，一般矩陣相關的題目也多是二維相關(不過像今天的封面圖的立方體，要表現立方體的儲存內容，就要用到三維矩陣)，我們今天討論的主要依據也是三維矩陣。

[[1,2,3],[4,5,6],[7,8,9]] 能夠表示一個
[1]-[2]-[3]
[4]-[5]-[6]
[7]-[8]-[9]
的二維陣列。

矩陣因為是由陣列組成，基本上陣列有的特性他也都有

• 僅能包含一種型別
• 二維矩陣會擁有長跟寬的概念(所以也能拿來表示圖的結構)
  今天只會探討矩陣本身的元素移動或建構模擬，圖的部分會留到後面討論到圖的時候再來深入討論。

相關常用演算法

老實說矩陣最常被提及應該還是在圖論相關的題目裡，在今天主要想要提到的是矩陣這個資料結構本身的建構和二維結構的特性。

模擬矩陣的遍歷和生成

Spiral Matrix
題目給定一個矩陣(二維陣列)，要求依螺旋的方式由外至內遍歷整個矩陣，並回傳一個陣列表示走訪元素的順序。這題是個很單純的模擬操作題，沒什麼特別的演算法，要特別注意的是不要有漏掉的元素，不要重複訪問相同元素 - 先列下遍歷步驟，按步驟來實現程式碼，那就沒問題。
1.假設給定的矩陣為 int[n][m]，表示直向高度為 n，橫向長度為 m 個元素
2.螺旋的方向是右、下、左、上重複這個訪問順序，將 startingRow, startingColumn 從左上 0,0 的位置開始
3.初始要走步數是該寬 / 高長度 -1 ，每個迴圈要走的距離 -2
4.除了正方形且邊長為偶數的情況下以外，按上面方式遍歷，都會留下一個長或寬為 1(或都是 1)的區域，最後用一個迴圈處理該區域

單純用講的可能有點抽象，這邊放圖舉例我上面的思路。
以一個 5 * 5 的矩陣，第一次遍歷的時候每邊要走 4(5 - 1的 結果)，第二次遍歷的時候每邊要走 2(4 - 2 的結果)，最後會剩下灰色的範圍，用一個額外的迴圈去走完。
類推如果是 4 * 4 的矩陣(沒有圖，想像一下)，第一次遍歷的時候每邊要走 3(4 - 1的 結果)，第二次遍歷的時候每邊要走 1(3 - 2 的結果)，因為是正方形且為邊長偶數，不會有最後灰色的區域。
注意要想一下自己的算法能不能處理如 1 * 10，或 2 * 10 這種長方形。

public class Solution {
    public IList<int> SpiralOrder(int[][] matrix) {
        var result = new List<int>();
        var startingRow = 0;
        var startingColumn = 0;
        var stepInRow = matrix.Length - 1;
        var stepInColumn = matrix[0].Length - 1;
        
        while((stepInRow > 0 && stepInColumn > 0) ){
            //To right
            for(var i = 0; i < stepInColumn; i++){
                result.Add(matrix[startingRow][startingColumn + i]);
            }
            //To bottom
            for(var i = 0; i < stepInRow; i++){
                result.Add(matrix[startingRow + i][startingColumn + stepInColumn]);
            }
            //To left
            for(var i = 0; i < stepInColumn && stepInRow > 0 ; i++){
                result.Add(matrix[startingRow + stepInRow][startingColumn + stepInColumn - i]);
            }
            //To top
            for(var i = 0; i < stepInRow && stepInColumn > 0; i++){
                result.Add(matrix[startingRow + stepInRow - i][startingColumn]);
            }

            startingRow++;
            startingColumn++;
            stepInRow = stepInRow - 2 > 0 ? stepInRow - 2 : 0;
            stepInColumn = stepInColumn - 2 > 0 ? stepInColumn - 2 : 0;
        }
        //Deal with one row / one column left situation
        if(result.Count != matrix.Length * matrix[0].Length){
            if(stepInRow == 0 && stepInColumn == 0){
                result.Add(matrix[startingRow][startingColumn]);
            }
            else{
                var i = 0;
                while(i <= stepInRow){
                    result.Add(matrix[startingRow + i][startingColumn]);
                    i++;
                }
                while(i <= stepInColumn){
                    result.Add(matrix[startingRow][startingColumn + i]);
                    i++;
                }
            }
        }
        return result;
    }
}

實作要注意的時候就是要避免把長度跟索引混用，會在很多比較或加減的地方容易混淆自己，要明確知道哪個變數代表的是索引，哪個是長度，不要在未經處理的狀況下讓索引跟長度比較。
這題其實每個人寫出來都會有些微的不同，重點就是要邏輯一致，我的寫法大概不是最乾淨的版本，但是我自己能夠理解的版本，總之就試寫一次，理輕自己的邏輯。
不建議死背別人的算法，這種直觀模擬題一般遇到了肯定是會按自己的思路來寫，如果不把自己的想法理清楚，因為一直不對就最後找了別人的解法來看來背，臨場寫不出來或有小漏洞的機會偏高。

題目不難，難的是怎麼在時間內寫得又快又好，能夠一次通過。
Spiral Matrix II 是這題的姊妹題，也可以寫寫看，如果這兩題都沒問題，那在矩陣遍歷和生成的處理應該可以應付了。

旋轉矩陣

Rotate Image
題目輸入會給一個矩陣，要求在不使用額外空間的情況下做矩陣的順時針 90 度旋轉。
這題如果完全沒見過，要靠自己想到又快又好的解法並不容易，但說破就不值錢。
[0,0] [0,1] [0,2]
[1,0] [1,1] [1,2]
[2,0] [2,1] [2,2]

1. 按左上到右下的這條對角線，將元素倆倆交換
   [0,0] [1,0] [2,0]
   [0,1] [1,1] [2,1]
   [0,2] [1,2] [2,2]
2. 將各列各自左右順序反轉
   [2,0] [1,0] [0,0]
   [2,1] [1,1] [0,1]
   [2,2] [1,2] [0,2]
   步驟就這麼簡單，原理在於觀察矩陣的兩個索引得來的規律，有興趣可以自己更深層的模擬一下。

public class Solution {
    public void Rotate(int[][] matrix) {
        for(var i = 0; i < matrix.Length; i++){
            for(var j = i; j < matrix[0].Length; j++){
                if(i != j){
                    (matrix[i][j], matrix[j][i]) = (matrix[j][i], matrix[i][j]);
                }
            }
        }
        for(var i = 0; i < matrix.Length; i++){
            for(var j = 0; j < matrix[0].Length/2; j++){
            //這段不用上面的寫法，是因為會變得很難閱讀
                var temp = matrix[i][j];
                var switchTo = matrix[0].Length - 1 - j;
                matrix[i][j] = matrix[i][switchTo];
                matrix[i][switchTo] = temp;
            }
        }
    }
}

做完如果想的遠一點，可能會想那往其他方向旋轉怎麼辦，其實就只是拿來對角線的線不一樣而已。
直接觀察原始矩陣和最後的矩陣，可以看到在同一列上發生了行列索引的自我交換和整列順序的左右交換，要做元素的行列索引自我交換就是透過對角線做翻轉，翻轉後行列索引就會倒過來，接著再做左右交換、就會變成最後的樣子。
如果看到旋轉，可能就要有意識和索引座標值的交換(也就是利用對角線做映射)連結，可以幫助你下次再遇到這題的時候想到這個解法。

今天的矩陣介紹就到這裡，目的在於讓大家複習矩陣的基本特性和遍歷模擬，後面矩陣會更頻繁地出現在各式問題裡，有這篇打基礎，後面要做矩陣的操作會比較紮實。